package com.lun.medium;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class DeepestLeavesSum {
	
	//方法一：DFS
    public int deepestLeavesSum(TreeNode root) {
        int[] sum = {0}, deepestLevel = {0};
        dfs(root, 0, sum, deepestLevel);
        return sum[0];
    }
    
    private void dfs(TreeNode node, int currentLevel, int[] sum, int[] deepestLevel) {
    	if(node == null) return;
    	
    	if(currentLevel >= deepestLevel[0]) {
    		if(currentLevel > deepestLevel[0]) {
	    		deepestLevel[0] = currentLevel;
	    		sum[0] = 0;
    		}
    		sum[0] += node.val;
    	}
    	
    	dfs(node.left, currentLevel + 1, sum, deepestLevel);
    	dfs(node.right, currentLevel + 1, sum, deepestLevel);
    }
    
    //方法二：BFS
    public int deepestLeavesSum2(TreeNode root) {
        int sum = 0;
    	LinkedList<TreeNode> queue = new LinkedList<>();
    	queue.offer(root);
        
    	while(!queue.isEmpty()) {
    		sum = 0;
    		for(int size = queue.size(); size > 0; size--) {
    			TreeNode node = queue.poll();
    			sum += node.val;
    			if(node.left != null)
    				queue.offer(node.left);
    			
    			if(node.right != null)
    				queue.offer(node.right);
    		}
    	}
        
    	return sum;
    }
    
}
